#include "event.h"
#include "processor.h"

guint
prov_node_hash_func (gconstpointer key) {
    guint hash = 0;
    const ProvNode *p = key;
    hash += g_str_hash (p->host);  
    hash += g_str_hash (p->type);
    hash += g_str_hash (p->name);
    return hash;
}

gboolean
prov_node_equal_func (gconstpointer a, gconstpointer b) {
    const ProvNode *pa = a;
    const ProvNode *pb = b;
    if (!g_strcmp0 (pa->host, pb->host) && !g_strcmp0 (pa->type, pb->type) &&
         !g_strcmp0 (pa->name, pb->name)) {
            return  TRUE;
    }
    return FALSE;
}

/* find the first node*/
ProvNode *
prov_node_find (Processor *pr,  ProvNode *hint) {
    return g_hash_table_lookup (pr->g.node_map, hint);
}

/* find active node */
ProvNode *
prov_node_find_active (Processor *pr, ProvNode * hint) {
    ProvNode *p = NULL;
    ProvNode *pf = prov_node_find (pr, hint);
    if (pf != NULL) {
        p = pf;
        while (p && p->active == FALSE) {
            p = p->next;
        }
    } else {
        p = NULL;
    }
    
    return p;
}

/* insert active node */
ProvNode *
prov_node_insert (Processor *p, gchar * host, gchar * type, gchar *name) {
        ProvNode *pn = g_new0 (ProvNode, 1);
        // use temp strings as identifier, need to dup them before inersting.
        pn->name = name;
        pn->type = type;
        pn->host = host;
        ProvNode *pf = prov_node_find (p,pn);
        if (pf == NULL) {
            pn->name = g_strdup (name);
            pn->type = g_strdup (type);
            pn->host = g_strdup (host);
            pn->active = TRUE;
            pn->id = p->g.id_base;
            p->g.id_base++;
            pn->in = NULL;
            pn->out = NULL;
            pn->next = NULL;
            g_ptr_array_add (p->g.prov_nodes, pn);
            g_hash_table_insert (p->g.node_map, pn, pn);
            // printf ("inserting :%s :%s\n", pn->name, pn->host);
            // fflush (stdout);
            return pn;
        } else {
            // before inserting new node, we need to find active node that has the same identifier.
            while (pf->next && pf->active == FALSE) {
                pf = pf->next;
            }
            if (pf->active == TRUE) {
                // if pf is active, we are inserting the same nodes repeatly, return pf;
                g_free (pn);
                return pf;
            } else {
                // otherwise, we need to insert new node into the list's tail.
                pn->name = g_strdup (name);
                pn->type = g_strdup (type);
                pn->host = g_strdup (host);
                pn->active = TRUE;
                pn->id = p->g.id_base;
                p->g.id_base++;
                pn->in = NULL;
                pn->out = NULL;
                pn->next = NULL;
                g_ptr_array_add (p->g.prov_nodes, pn);
                // printf ("inserting :%s :%s\n", pn->name, pn->host);
                // fflush (stdout);
                pf->next = pn;
                return pn;
            }
        }
        return NULL;
}

int
prov_node_terminate (Processor *p,  gchar * host,
                                       gchar * type,  gchar *name) {
    ProvNode hint, *pn = &hint;
    pn->name = name;
    pn->host = host;
    pn->type = type;
    ProvNode *pf = prov_node_find_active (p, pn);
    if (pf != NULL) {
        pf->active = FALSE;
    }
    return 0;
}

// static int
// prov_node_destructor (Processor *p, ProvNode *pn) {
//     // warning: this func may destroy the entire map.
//     g_free (pn->host);
//     g_free (pn->type);
//     g_free (pn->name);
//     g_ptr_array_unref (pn->in);
//     g_ptr_array_unref (pn->out);
//     g_free (pn);
//     // g_ptr_array_remove (p->g.prov_nodes, pn);
//     // p->g.prov_nodes has all the ProvNodes, so ignore pn->next
//     // TODO: remove all the refs point to this node.
//     return 0;
// }


gint edge_to_cmp_func (gconstpointer a, gconstpointer b) {
    const ProvEdge *ea = a, *eb = b;
    if (ea->to == eb->to && !g_strcmp0 (eb->type, ea->type)) {
        return 0;
    } else {
        return 1;
    }
}

gint edge_from_cmp_func (gconstpointer a, gconstpointer b) {
    const ProvEdge *ea = a, *eb = b;
    if (ea->from == eb->from && !g_strcmp0 (eb->type, ea->type)) {
        return 0;
    } else {
        return 1;
    }
}

int
prov_node_connect (Processor *p, ProvNode *from, ProvNode *to,  gchar * type) {
    size_t iter;
    ProvEdge *e, *new_e;
    new_e = g_new(ProvEdge, 1);
    new_e->to = to;
    new_e->from = from;
    new_e->type = g_strdup(type);
    //new_e->type = g_strdup (type);
    gboolean added = FALSE;
    /*for from node*/
    if (!g_slist_find_custom (from->out, new_e, edge_to_cmp_func)) {
        from->out = g_slist_prepend (from->out, new_e);
        added = TRUE;
    }
    if (!g_slist_find_custom (to->in, new_e, edge_from_cmp_func)) {
        to->in =g_slist_prepend (to->in, new_e);
        added = TRUE;
    }
    out:
    if (added == FALSE) {
        g_free (new_e->type);
        g_free (new_e);
    } else {
        g_ptr_array_add (p->g.prov_edges, new_e);
    }
    return 0;
}

Processor *
processor_create (void *opaque, void(*destructor)(void*), GHashFunc hfunc, GEqualFunc efunc) {
    Processor *p;
    p = g_new0 (Processor, 1);
    bzero (&(p->g), sizeof (ProvGraph));
    p->g.id_base = 1;
    p->g.prov_nodes = g_ptr_array_sized_new (819200);
    p->g.prov_edges =  g_ptr_array_sized_new (819200);
    p->g.node_map = g_hash_table_new (hfunc, efunc);
    p->destructor = destructor;
    p->opaque = opaque;
    // TODO: insufficient memory.
    return p;
}


void
processor_destructor (Processor *p) {
    guint iter;
    ProvEdge *pe = NULL;
    ProvNode *pn = NULL;
    p->destructor (p->opaque);
    for (iter = 0; iter < p->g.prov_edges->len; iter++) {
        pe = p->g.prov_edges->pdata[iter];
        g_free (pe->type);
        g_free (pe);
    }
    for (iter = 0; iter < p->g.prov_nodes->len; iter++) {
        pn = p->g.prov_nodes->pdata[iter];
        g_free (pn->host);
        g_free (pn->type);
        g_free (pn->name);
        g_slist_free (pn->in);
        g_slist_free (pn->out);
        // g_ptr_array_unref (pn->in);
        // g_ptr_array_unref (pn->out);
        g_free (pn);
    }

    g_ptr_array_unref (p->g.prov_edges);
    g_ptr_array_unref (p->g.prov_nodes);
    g_hash_table_unref (p->g.node_map);
}

/*if @in is true, we will traverse the graph until we visit all source nodes */
int
processor_traverse (Processor *p, void *gen,  gchar *host,  gchar *name,  gchar * type,gboolean in, TravelCB *cb) {
    GHashTable *visited_node = g_hash_table_new (g_direct_hash, g_direct_equal);
    GHashTable *visited_edge = g_hash_table_new (g_direct_hash, g_direct_equal);
    ProvNode tmp_pn =  {
        .host = host,
        .name = name,
        .type = type
    }, *hint = &tmp_pn;
    ProvNode *pn = g_hash_table_lookup (p->g.node_map, hint), *prev_pn, *this_pn;
    ProvEdge *pe;
    if (pn == NULL) {
        fprintf (stderr, "Node not found: {host=%s, name=%s, type=%s}\n", host, name, type);
        g_hash_table_unref (visited_node);
        return -1;
    } 
    // bfs
    GQueue *pn_que = g_queue_new (); 
    GSList *iter;
    g_queue_push_tail (pn_que, pn);
    if (in == TRUE) {
        while (g_queue_get_length (pn_que) != 0) {
            prev_pn = g_queue_pop_head (pn_que);
            g_hash_table_insert (visited_node, prev_pn, prev_pn);
            for (iter = prev_pn->in; iter != NULL; iter = iter->next) {
                pe = iter->data;
                this_pn = pe->from;
                if (!g_hash_table_contains (visited_edge, pe)) {
                    g_hash_table_insert (visited_edge, pe, pe);
                    cb (gen, this_pn, prev_pn, pe->type);
                    if (!g_hash_table_contains (visited_node, this_pn)) {
                        g_hash_table_insert (visited_node, this_pn, this_pn);
                        g_queue_push_tail (pn_que, this_pn);
                    }
                }
            }
        }
    } else {
         while (g_queue_get_length (pn_que) != 0) {
            prev_pn = g_queue_pop_head (pn_que);
            g_hash_table_insert (visited_node, prev_pn, prev_pn);
            for (iter = prev_pn->out; iter!= NULL; iter= iter->next) {
                pe = iter->data;
                this_pn = pe->to;
                if (!g_hash_table_contains (visited_edge, pe)) {
                    g_hash_table_insert (visited_edge, pe, pe);
                    cb (gen, prev_pn, this_pn, pe->type);
                    if (!g_hash_table_contains (visited_node, this_pn)) {
                        g_hash_table_insert (visited_node, this_pn, this_pn);
                        g_queue_push_tail (pn_que, this_pn);
                    }
                }
            }
        }
    }
    out:
    return 0;
}

/*if @in is true, we will traverse the graph until we visit all source nodes */
int
processor_traverse_regex (Processor *p, void *gen,gchar *host_rx_str,  gchar *name_rx_str,  gchar * type,gboolean in, TravelCB *cb) {
    GHashTable *visited_node = g_hash_table_new (g_direct_hash, g_direct_equal);
    GHashTable *visited_edge = g_hash_table_new (g_direct_hash, g_direct_equal);
    ProvEdge *pe;
    ProvNode*pn,*prev_pn, *this_pn;
    // bfs
    GQueue *pn_que = g_queue_new (); 
    GSList *iter;
    GSList *adj_node;
    guint pn_iter;
    GRegex *host_rx, *name_rx;
    host_rx = g_regex_new (host_rx_str, G_REGEX_DEFAULT, G_REGEX_MATCH_DEFAULT, NULL);
    name_rx = g_regex_new (name_rx_str, G_REGEX_DEFAULT, G_REGEX_MATCH_DEFAULT, NULL);
    for (pn_iter=0; pn_iter < p->g.prov_nodes->len; pn_iter++) {
        pn = p->g.prov_nodes->pdata[pn_iter];
        if(g_hash_table_contains (visited_node, pn))
                continue;
        if (g_regex_match (host_rx, pn->host, G_REGEX_MATCH_DEFAULT, NULL) && 
             g_regex_match (name_rx, pn->name, G_REGEX_MATCH_DEFAULT, NULL)){
            if (type != NULL) {
                if (g_strcmp0 (pn->type, type) != 0)
                    continue;
            }
            g_queue_push_tail (pn_que, pn);
            if (in == TRUE) {

                while (g_queue_get_length (pn_que) != 0) {
                    prev_pn = g_queue_pop_head (pn_que);
                    g_hash_table_insert (visited_node, prev_pn, prev_pn);
                    adj_node = NULL;
                    for (iter = prev_pn->in; iter != NULL; iter=iter->next) {
                        pe = iter->data;
                        this_pn = pe->from;
                        /* optimize */
                        if (this_pn->in == NULL) continue;
                        if (g_slist_find (adj_node, ((ProvEdge *)(this_pn->in->data))->from)) {
                            continue;
                        } 
                        if (strstr (this_pn->name, "System") != NULL)
                            continue;

                        adj_node = g_slist_append (adj_node,  ((ProvEdge *)(this_pn->in->data))->from);
                        if (!g_hash_table_contains (visited_edge, pe)) {
                            g_hash_table_insert (visited_edge, pe, pe);
                            cb (gen,this_pn, prev_pn,  pe->type);
                            if (!g_hash_table_contains (visited_node, this_pn)) {
                                g_hash_table_insert (visited_node, this_pn, this_pn);
                                g_queue_push_tail (pn_que, this_pn);
                            }
                        }
                    }
                    g_slist_free (adj_node);
                }
            } else {
                while (g_queue_get_length (pn_que) != 0) {
                    prev_pn = g_queue_pop_head (pn_que);
                    g_hash_table_insert (visited_node, prev_pn, prev_pn);
                    adj_node = NULL;
                    for (iter = prev_pn->out; iter != NULL; iter=iter->next) {
                        pe = iter->data;
                        this_pn = pe->to;
                        /* optimize */
                        if (this_pn->out == NULL) continue;
                        if (g_slist_find (adj_node, ((ProvEdge *)(this_pn->in->data))->to)) {
                            continue;
                        } 
                        adj_node = g_slist_append (adj_node,  ((ProvEdge *)(this_pn->in->data))->to);
                        if (strstr (this_pn->name, "System") != NULL)
                            continue;      

                        if (!g_hash_table_contains (visited_edge, pe)) {
                            g_hash_table_insert (visited_edge, pe, pe);
                            cb (gen, prev_pn, this_pn, pe->type);
                            if (!g_hash_table_contains (visited_node, this_pn)) {
                                g_hash_table_insert (visited_node, this_pn, this_pn);
                                g_queue_push_tail (pn_que, this_pn);
                            }
                        }
                    }
                    g_slist_free (adj_node);
                }
            }
        }
    }
    g_regex_unref (host_rx);
    g_regex_unref (name_rx);
    out:
    return 0;
}


int
processor_traverse_regex_bidirectional (Processor *p, void *gen,gchar *host_rx_str,  gchar *name_rx_str,  gchar * type, TravelCB *cb) {
    GHashTable *visited_node = g_hash_table_new (g_direct_hash, g_direct_equal);
    GHashTable *visited_edge = g_hash_table_new (g_direct_hash, g_direct_equal);
    ProvEdge *pe;
    ProvNode*pn,*prev_pn, *this_pn;
    // bfs
    GQueue *pn_que = g_queue_new (); 
    GSList *iter;
    GSList *adj_node;
    guint pn_iter;
    GRegex *host_rx, *name_rx;
    host_rx = g_regex_new (host_rx_str, G_REGEX_DEFAULT, G_REGEX_MATCH_DEFAULT, NULL);
    name_rx = g_regex_new (name_rx_str, G_REGEX_DEFAULT, G_REGEX_MATCH_DEFAULT, NULL);
    for (pn_iter=0; pn_iter < p->g.prov_nodes->len; pn_iter++) {
        pn = p->g.prov_nodes->pdata[pn_iter];
        if(g_hash_table_contains (visited_node, pn))
                continue;
        if (g_regex_match (host_rx, pn->host, G_REGEX_MATCH_DEFAULT, NULL) && 
             g_regex_match (name_rx, pn->name, G_REGEX_MATCH_DEFAULT, NULL)){
            if (type != NULL) {
                if (g_strcmp0 (pn->type, type) != 0)
                    continue;
            }
            g_queue_push_tail (pn_que, pn);
            while (g_queue_get_length (pn_que) != 0) {
                prev_pn = g_queue_pop_head (pn_que);
                g_hash_table_insert (visited_node, prev_pn, prev_pn);
                adj_node = NULL;
                for (iter = prev_pn->in; iter != NULL; iter=iter->next) {
                    pe = iter->data;
                    this_pn = pe->from;
                    /* optimize */
                    //if (this_pn->in == NULL) continue;
                     if (this_pn->in != NULL) {
                        if (g_slist_find (adj_node, ((ProvEdge *)(this_pn->in->data))->from)) {
                            continue;
                        } 
                        adj_node = g_slist_append (adj_node,  ((ProvEdge *)(this_pn->in->data))->from);
                    }
                    if (strstr (this_pn->name, "System") != NULL)
                        continue;
                    if (!g_hash_table_contains (visited_edge, pe)) {
                        g_hash_table_insert (visited_edge, pe, pe);
                        cb (gen,this_pn, prev_pn,  pe->type);
                        if (!g_hash_table_contains (visited_node, this_pn)) {
                            g_hash_table_insert (visited_node, this_pn, this_pn);
                            g_queue_push_tail (pn_que, this_pn);
                        }
                    }
                }
                g_slist_free (adj_node);
                adj_node = NULL;
                for (iter = prev_pn->out; iter != NULL; iter=iter->next) {
                    pe = iter->data;
                    this_pn = pe->to;
                    /* optimize */
                    //if (this_pn->out == NULL) continue;
                    if (this_pn->out != NULL) {
                        if (g_slist_find (adj_node, ((ProvEdge *)(this_pn->out->data))->to)) {
                            continue;
                        }
                        adj_node = g_slist_append (adj_node,  ((ProvEdge *)(this_pn->out->data))->to);
                    }
                    if (strstr (this_pn->name, "System") != NULL)
                        continue;      

                    if (!g_hash_table_contains (visited_edge, pe)) {
                        g_hash_table_insert (visited_edge, pe, pe);
                        cb (gen, prev_pn, this_pn, pe->type);
                        if (!g_hash_table_contains (visited_node, this_pn)) {
                            g_hash_table_insert (visited_node, this_pn, this_pn);
                            g_queue_push_tail (pn_que, this_pn);
                        }
                    }
                }
                g_slist_free (adj_node);
            }
        }
    }
    g_regex_unref (host_rx);
    g_regex_unref (name_rx);
    out:
    return 0;
}

int
processor_traverse_regex_point2point (Processor *p, void *gen, gchar *src_host_rx_str,  gchar *src_name_rx_str,  gchar * src_type, 
                                                                                gchar *tgt_host_rx_str,  gchar *tgt_name_rx_str,  gchar * tgt_type,TravelCB *cb) {
    GHashTable *visited_node = g_hash_table_new (g_direct_hash, g_direct_equal);
    GHashTable *visited_edge = g_hash_table_new (g_direct_hash, g_direct_equal);
    GHashTable *processed_edge = g_hash_table_new (g_direct_hash, g_direct_equal);
    GHashTable *reachable_node = g_hash_table_new (g_direct_hash, g_direct_equal);
    ProvEdge *pe;
    ProvNode*pn,*prev_pn, *this_pn;
    // bfs
    GQueue *pn_stk = g_queue_new ();
    GQueue *pe_stk = g_queue_new ();
    GQueue *trace_stk = g_queue_new ();

    GSList *pe_list, *new_pe;
    GList *iter;
    GSList *adj_node;
    guint pn_iter;
    GRegex *src_host_rx, *src_name_rx, *tgt_host_rx, *tgt_name_rx;
    src_host_rx = g_regex_new (src_host_rx_str, G_REGEX_DEFAULT, G_REGEX_MATCH_DEFAULT, NULL);
    src_name_rx = g_regex_new (src_name_rx_str, G_REGEX_DEFAULT, G_REGEX_MATCH_DEFAULT, NULL);
    tgt_host_rx = g_regex_new (tgt_host_rx_str, G_REGEX_DEFAULT, G_REGEX_MATCH_DEFAULT, NULL);
    tgt_name_rx = g_regex_new (tgt_name_rx_str, G_REGEX_DEFAULT, G_REGEX_MATCH_DEFAULT, NULL);
    

    for (pn_iter=0; pn_iter < p->g.prov_nodes->len; pn_iter++) {
        pn = p->g.prov_nodes->pdata[pn_iter];
        if (g_regex_match (src_host_rx, pn->host, G_REGEX_MATCH_DEFAULT, NULL) && 
             g_regex_match (src_name_rx, pn->name, G_REGEX_MATCH_DEFAULT, NULL)){
            if (src_type != NULL) {
                if (g_strcmp0 (pn->type, src_type) != 0)
                    continue;
            }
            g_queue_push_head (pn_stk, pn);
            g_queue_push_head (pe_stk, pn->out);

            while (g_queue_get_length (pn_stk) != 0) {
                pn = g_queue_peek_head (pn_stk);
                pe_list = g_queue_peek_head (pe_stk);
                if ((g_regex_match (tgt_host_rx, pn->host, G_REGEX_MATCH_DEFAULT, NULL) &&
                    g_regex_match (tgt_name_rx, pn->name, G_REGEX_MATCH_DEFAULT, NULL)) || 
                    (g_hash_table_contains (reachable_node, pn))) {
                        if (tgt_type == NULL ||  !g_strcmp0(pn->type, tgt_type) ||g_hash_table_contains (reachable_node, pn)) {
                            // match
                            iter = trace_stk->tail;
                            while (iter != NULL) {
                                pe = iter->data;
                                if (!g_hash_table_contains (processed_edge, pe)) {
                                    cb (gen, pe->from, pe->to, pe->type);
                                    g_hash_table_insert (processed_edge, pe, pe);
                                    g_hash_table_insert (reachable_node, pe->from, pe->from);
                                }
                                iter = iter->prev;
                            }
                            g_queue_pop_head (pn_stk);
                            g_queue_pop_head (pe_stk);
                            g_queue_pop_head (trace_stk);
                            continue;
                        }
                }
                /* we have visited pn*/
                if (g_queue_get_length (pe_stk) == 0) {
                    g_assert_not_reached ();
                }
                if (pe_list == NULL) {
                    g_queue_pop_head (pn_stk);
                    g_queue_pop_head (pe_stk);
                    g_queue_pop_head (trace_stk);
                } else {
                    /* last node*/
                    pe = pe_list->data;
                    g_queue_pop_head (pe_stk);
                    g_queue_push_head (pe_stk, pe_list->next);
                    if (g_hash_table_contains (visited_edge, pe))
                        continue;
                    g_hash_table_insert (visited_edge, pe, pe);
                    /* go deeper*/
                    g_queue_push_head (trace_stk, pe);
                    g_queue_push_head (pn_stk, pe->to);
                    g_queue_push_head (pe_stk, pe->to->out);
                }
            }
        }
    }
    g_regex_unref (src_host_rx);
    g_regex_unref (src_name_rx);
    g_regex_unref (tgt_host_rx);
    g_regex_unref (tgt_name_rx);
    out:
    return 0;
}


int
processor_traverse_all (Processor *p, void *gen, TravelCB *cb) {
    GHashTable *visited_node = g_hash_table_new (g_direct_hash, g_direct_equal);
    GHashTable *visited_edge = g_hash_table_new (g_direct_hash, g_direct_equal);
    ProvNode *pn,  *prev_pn, *this_pn;
    // bfs
    ProvEdge *pe;
    GQueue *pn_que = g_queue_new (); 
    guint iter;
    GSList *niter;
    for (iter = 0; iter < p->g.prov_nodes->len; iter++) {
        pn = p->g.prov_nodes->pdata[iter];
        if(!g_hash_table_contains (visited_node, pn)) {
            g_queue_push_tail (pn_que, pn);
            while (g_queue_get_length (pn_que) != 0) {
                prev_pn = g_queue_pop_head (pn_que);
                g_hash_table_insert (visited_node, prev_pn, prev_pn);
                for (niter = prev_pn->out; niter != NULL; niter = niter->next) {
                    pe = niter->data;
                    this_pn = pe->to;
                    if (!g_hash_table_contains (visited_edge, pe)) {
                        g_hash_table_insert (visited_edge, pe, pe);
                        cb (gen, prev_pn, this_pn, pe->type);
                        if (!g_hash_table_contains (visited_node, this_pn)) {
                            g_hash_table_insert (visited_node, this_pn, this_pn);
                            g_queue_push_tail (pn_que, this_pn);
                        }
                    }
                }
            }
        }
    }
    g_queue_free (pn_que);
    g_hash_table_unref (visited_edge);
    g_hash_table_unref (visited_node);
    out:
    return 0;
}
